<?php
/**
 *  链表习题
 */

namespace Xxb\XxbPhpAlgo\Topic;

use Xxb\XxbPhpAlgo\SingleLinkedList;
use Xxb\XxbPhpAlgo\SingleLinkedListNode;

class LinkedListExercises
{
    public function reverseLinkedList(SingleLinkedList $target)
    {
        if ($target->isEmpty()) {
            throw new \RuntimeException('empty linked list.');
        }

        $this->reverseByRecurse($target->getHead(), $target);
        return $target;
    }

    /**
     * @param SingleLinkedListNode|null $node
     * @param SingleLinkedList|null $target
     *
     * @return SingleLinkedListNode|null
     */
    protected function reverseByRecurse($node, $target)
    {
        if (is_null($node->getNext())) {
            $target->setHead($node);
            return $node;
        }
        $retNode = $this->reverseByRecurse($node->getNext(), $target);
        $retNode->setNext($node);

        return $node;
    }


    /**
     * 翻转链表：
     * 从头节点开始向下遍历，遍历出来的结点，作为新链表的头结点即可
     *
     * @return bool
     */
    //public function reverseLinkedList()
    //{
    //    if (empty($this->head)) {
    //        return false;
    //    }
    //    $newHead = null;
    //    while (!empty($this->head)) {
    //        if (empty($newHead)) {
    //            $newHead = new SingleLinkedListNode($this->head->value);
    //        } else {
    //            $newHead = new SingleLinkedListNode($this->head->value, $newHead);
    //        }
    //        $this->head = $this->head->next;
    //    }
    //    $this->head = $newHead;
    //    return true;
    //}

    /**
     * 翻转链表:
     * 通过递归的方式
     * @param null $newHead
     *
     * @return null
     */
    //public function recurseReverseLinkedList($newHead = null)
    //{
    //    if (empty($this->head)) {
    //        $this->head = $newHead;
    //        return null;
    //    }
    //    if (empty($newHead)) {
    //        $newHead = new SingleLinkedListNode($this->head->value);
    //    } else {
    //        $newHead = new SingleLinkedListNode($this->head->value, $newHead);
    //    }
    //    $this->head = $this->head->next;
    //    return $this->recurseReverseLinkedList($newHead);
    //}
}
